
import java.util.*;
import java.lang.Math.*;

public class AllMatchMC {

  Graph graph;
  Set<Edge> matching;
  int mix;
  int mix2;
  boolean relaxed=false;

  public AllMatchMC(Graph g,double eta) {
    this.graph = g;
    this.matching = new HashSet();
    setMixingTime(eta);
  }

  //this is the function that transitions the matching
  public void takeStep() {
    //randomly select our edge
    Edge e = graph.edges.get((int) (Math.random() * graph.edges.size()));
    Set<Edge> m=matching;

    List<Edge> toRemove=new ArrayList();
    for (Edge x : m) {
      if (x.from==e.from || x.to==e.from|| x.from==e.to||x.to==e.from)
      toRemove.add(x);
    }

    //if the edge is already there, drop it
    if (m.contains(e)) {
        m.remove(e);
    } else {
        m.add(e);
    } 
    m.removeAll(toRemove);

  }

  public void setMixingTime(double eta) {
    int n = this.graph.vertices.length;
    int m = this.graph.edges.size();

    mix= (int)(n * m * ( Math.log(Math.pow(eta,-1)) +  n * Math.log(n))); 
    mix2= (int)(n * m * ( Math.log(Math.pow(eta,-1)))); //relaxation
    relaxed=false;

  }

  public int getMixingTime(){

    return mix;

  }

  public int getRelaxedMixingTime(){

    return mix2;

  }

  public Set<Edge> randomSample(double eta){

    int mixtime;
    if(relaxed){
      mixtime=mix2;
    }
    else{
      mixtime=mix;
    }

    for (int i = 0; i < mixtime; i++){
      // transition mixingTime times to get a good matching    
      takeStep();
    }
    relaxed=true;
    return this.matching;
  }

  public LinkedList<Set<Edge>> generateSamples(int n, double eta){
    LinkedList<Set<Edge>> out = new LinkedList<Set<Edge>>();
    for (int i = 0; i < n; i++){
      out.add(randomSample(eta));
    }
    return out;
  }

  public static void main(String args[]) {
    Graph g = Graph.kgraphgen(10);
    System.out.println(g);
    AllMatchMC mc = new AllMatchMC(g,.1);
    for (int i = 0; i < (50); i++) {
      mc.takeStep();
      System.out.println(mc.matching);
    }
  }
}
